package 简单.滑动窗口;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA
 * 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
 * <p>
 * 编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/repeated-dna-sequences
 */
public class 重复的DNA序列_187 {

    public static void main(String[] args) {
        String s = "AAAAAAAAAAA";
        System.out.println(findRepeatedDnaSequences(s));
    }

    /**
     * 哈希表
     *
     * @param s
     * @return
     */
    public static List<String> findRepeatedDnaSequences(String s) {
        //用一个set来接收不重复的结果
        Set<String> result = new HashSet<>();
        Set<String> set = new HashSet<>();
        //长度大于10才能有重复的可能
        if (s.length() > 10) {
            for (int i = 0; i <= s.length() - 10; i++) {
                //如果不能添加进去，就是重复元素
                if (set.add(s.substring(i, i + 10)) == false) {
                    result.add(s.substring(i, i + 10));
                }
            }
        }
        return new ArrayList<>(result);
    }

    //TODO 哈希表+滑动窗口+位运算？？？
}
